package ext;

import java.util.*;
import org.junit.*;


public class ByteX {
    //圆环归位问题
    /* 
        圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。
        输入: 2
        输出: 2
        解释：有2种方案。分别是0->1->0和0->9->0
    */
    public int countMethods(int n) {
        f = new int[10][n + 1];
        for (int i = 0; i < f.length; i++) {
            Arrays.fill(f[i], -1);
        }
        return dfs(0, n);
    }

    //记忆化搜索：记录当前位置和次数，若f[i][j] >= 0就直接返回
    int[][] f;
    public int dfs(int i, int j) {
        if (i < 0 || i > 9) return 0;
        if (f[i][j] >= 0) {
            return f[i][j];
        }
        if (j == 0) {
            return i == 0 ? 1 : 0;
        }
        if (i > j && 10 - i > j) { //肯定回不去了，剪枝
            f[i][j] = 0;
            return f[i][j];
        }
        //当前向前或者相后一步
        int forward = i + 1 > 9 ? 0 : i + 1;
        int back = i - 1 < 0 ? 9 : i - 1;
        f[i][j] = dfs(forward, j - 1) + dfs(back, j - 1);
        return f[i][j];
    }

    public int countMethods2(int n) {
        int[][] f = new int[n + 1][10];
        f[0][0] = 1;
        //f[i][0] = 0； i != 0
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 10; j++) {
                f[i][j] = f[i - 1][(j - 1 + 10) % 10] + f[i - 1][(j + 1 + 10) % 10];
            }
        }
        return f[n][0];
    }

    @Test
    public void test() {
        System.out.println(countMethods(2));
        for (int i = 0; i < 10; i++) {
            System.out.println(countMethods(i) == countMethods2(i));
        }
    }

    //循环依赖
    /* 
        现有n个编译项，编号为0 ~ n-1。给定一个二维数组，表示编译项之间有依赖关系。如[0, 1]表示1依赖于0。
        若存在循环依赖则返回空；不存在依赖则返回可行的编译顺序。
    */
    public List<Integer> compile(int[][] nums, int n) {
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();

        int len = nums.length;
        Map<Integer, Set<Integer>> nexts  = new HashMap<>(); //有多少个序号依赖这个序号
        Map<Integer, Integer> map  = new HashMap<>(); //当前序号依赖的序号个数
        for (int i = 0; i < len; i++) {
            map.put(nums[i][1], map.getOrDefault(nums[i][1], 0));
            if (!nexts.containsKey(nums[i][0])) {
                Set<Integer> set = new HashSet<>();
                set.add(nums[i][1]);
                nexts.put(nums[i][0], set);
            } else {
                nexts.get(nums[i][0]).add(nums[i][1]);
            }
        }
        for (int i = 0; i < n - 1; i++) {
            if (!map.containsKey(i)) { //初始点
                queue.offer(i);
            }
        }

        int cur;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            res.add(cur);
            Set<Integer> s = nexts.get(cur);
            Set<Integer> set = new HashSet<>(s);
            for (int t: set) {
                int k = map.get(t) - 1;
                if (k == 0) {
                    s.remove(t);
                    queue.offer(t);
                    map.remove(t);
                } else {
                    map.put(t, k);
                }
            }
        }
        return map.isEmpty() ? res : new ArrayList<>();
    }


    //0~m-1共m个数，从0开始触发，走n步回到0的可能的方案数
    public int cycleBack(int m, int n) {
        int[][] f = new int[m][n + 1];
        //f[i][0] = 0; f[0][0] = 1;
        f[0][0] = 1;
        for (int j = 1; j <= n; j++) {
            for (int i = 0; i < m; i++) {
                int right = (i + 1) % m,
                    left = (i - 1 + m) % m;
                f[i][j] = f[right][j - 1] + f[left][j - 1];
            }
        }

        return f[0][n];
    }

    @Test
    public void tes4t() {
        System.out.println(cycleBack(10, 2));
    }
}
